package org.example.myleet.p1584;

import java.util.*;

public class Solution1 {
    /**
     * 522 ms
     * O(n^n * log(n))
     * Kruskal算法
     * 从边的角度利用排序的方式将最小的边加入到图中
     */
    public int minCostConnectPoints(int[][] points) {
        if (points.length < 2) {
            return 0;
        }
        //初始化所有的边，并计算cost
        List<Edge> edges = new ArrayList<>();
        for (int i=0; i<points.length; i++) {
            for (int j=i+1; j<points.length; j++) {
                int cost = manhattanDistance(points, i, j);
                Edge edge = new Edge(i, j, cost);
                edges.add(edge);
            }
        }
        //将所有边按从小到大的顺序排序
        edges.sort(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.cost - o2.cost;
            }
        });
        //利用并查集检查边的两点是否连通
        UnionFind uf = new UnionFind(points.length);
        //先将最小cost的边加入并查集中，连通两个点
        Edge edge0 = edges.get(0);
        uf.union(edge0.p1, edge0.p2);
        int totalCost = edge0.cost;
        for (int i=1; i<edges.size(); i++) {
            //按cost递增顺序取出边，如果边所连接的点处于两个不同的集合中，则应用这条边，将两点在并查集中连起来，累加cost
            Edge edge = edges.get(i);
            if (uf.find(edge.p1) != uf.find(edge.p2)) {
                uf.union(edge.p1, edge.p2);
                totalCost += edge.cost;
            }
        }
        return totalCost;
    }

    /**
     * 并查集
     */
    static class UnionFind {
        int[] parent;

        public UnionFind(int len) {
            parent = new int[len];
            for (int i=0; i<len; i++) {
                parent[i] = i;
            }
        }

        public int find(int p) {
            int f = parent[p];
            if (f != p) {
                parent[p] = find(f);
            }
            return parent[p];
        }

        public void union(int p1, int p2) {
            int rootP1 = find(p1);
            int rootP2 = find(p2);
            if (rootP1 == rootP2) {
                return;
            }
            parent[rootP1] = rootP2;
        }
    }

    static int manhattanDistance(int[][] points, int p1, int p2) {
        return Math.abs(points[p1][0] - points[p2][0]) + Math.abs(points[p1][1] - points[p2][1]);
    }

    static class Edge implements Comparable<Edge> {
        int p1;
        int p2;
        int cost;

        public Edge(int p1, int p2, int cost) {
            this.p1 = p1;
            this.p2 = p2;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return this.cost - o.cost;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Edge edge = (Edge) o;
            return p1 == edge.p1 &&
                    p2 == edge.p2;
        }

        @Override
        public int hashCode() {
            return Objects.hash(p1, p2);
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("Edge{");
            sb.append("p1=").append(p1);
            sb.append(", p2=").append(p2);
            sb.append(", cost=").append(cost);
            sb.append('}');
            return sb.toString();
        }
    }
}
